package leetcode.algorithm;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

/**
 * 本类是树的非递归遍历的所有方式
 * @author jiangwz
 * @create 2019/11/12.
 */
public class TreeSearchAnyway {

//                    5
//                   / \
//                 3    6
//                / \    \
//               2   4    8
//              /        / \
//             1        7   9
    public static void main(String[] args){
        TreeSearchAnyway t = new TreeSearchAnyway();
        Integer[] arr = new Integer[]{5,3,6,2,4,null,8,1,null,null,null,null,null,7,9};
        TreeNode treeNode = TreeHelper.array2Tree(arr);

//        System.out.println(t.preOrderTraversal(treeNode));//非递归先序遍历二叉树 stack
//        System.out.println(t.inOrderTraversal(treeNode));// 树的中序遍历非递归方式
//        System.out.println(t.postOrderTraversal(treeNode));//树的后续遍历非递归  linkedList
//        System.out.println(t.postOrderTraversal2(treeNode));//树的后续遍历非递归 stack

//        System.out.println(t.levelOrder(treeNode));//非递归层序遍历二叉树 linkedList
    }

    /**
     * 非递归先序遍历二叉树 stack
     * */
    public List<Integer> preOrderTraversal(TreeNode root) {
        List<Integer> resultList=new ArrayList<>();
        Stack<TreeNode> treeStack=new Stack<>();
        if(root==null) //如果为空树则返回
            return resultList;
        treeStack.push(root);
        while(!treeStack.isEmpty()){
            TreeNode tempNode=treeStack.pop();
            if(tempNode!=null){
                resultList.add(tempNode.val);//访问根节点
                treeStack.push(tempNode.right); //入栈右孩子
                treeStack.push(tempNode.left);//入栈左孩子
            }
        }
        return resultList;
    }



    // 树的中序遍历非递归 (重点)
    public List<Integer> inOrderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode cur = root;

        while(cur!=null || !stack.empty()){
            while(cur!=null){
                stack.add(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            list.add(cur.val);
            cur = cur.right;
        }
        return list;
    }

    /**
     * 用链表的方式后续遍历
     * @param root
     * @return
     */
    public List<Integer> postOrderTraversal(TreeNode root) {
        LinkedList<TreeNode> stack = new LinkedList<>();
        LinkedList<Integer> output = new LinkedList<>();
        if (root == null) {
            return output;
        }

        stack.add(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pollLast();
            output.addFirst(node.val);
            if (node.left != null) {
                stack.add(node.left);
            }
            if (node.right != null) {
                stack.add(node.right);
            }
        }
        return output;
    }





    /**
     * 用栈的方式后续非递归遍历
     * @param root
     * @return
     */
    public List<Integer> postOrderTraversal2(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        LinkedList<Integer> output = new LinkedList<>();
        if (root == null) {
            return output;
        }

        stack.add(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            output.addFirst(node.val);
            if (node.left != null) {
                stack.add(node.left);
            }
            if (node.right != null) {
                stack.add(node.right);
            }

        }
        return output;
    }



    /**
     * 树的层序遍历非递归 LinkedList
     * @param root
     * @return
     */
    public List<Integer> levelOrder(TreeNode root){
        List<Integer> resultList=new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if (root == null)
            return null;
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode n = queue.poll();
            if (n!= null) {
                resultList.add(n.val);
                queue.add(n.left);
                queue.add(n.right);
            }
        }
        return resultList;
    }
}
